package leecode.array.数组其他问题;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangxi created on 2021/6/6 23:10
 * @version v1.0
 *
 * nowcoder
 *
 * 未排序数组中累加和为给定值的最长子数组长度
 *
 * 给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度
 *
 * 仍利用前缀和，与此题解法思想一致 SubarraySumEqualsK
 */
public class MaxlenEqualK {


    /**
     * 此题比较难的点是初始化 sum=0的k-v值，
     * 因为是两个窗口相减，比如 A~C - A~B，其中元素个数即B~C 子数组长度元素总和，不需要额外再加1，
     * 和单纯的下标index相减还不一样。
     */

    public int maxlenEqualK (int[] arr, int k) {
        if (arr == null || arr.length <= 0) {
            return 0;
        }
        Map<Integer, Integer> preSumDict = new HashMap<>();
        preSumDict.put(0, -1);
        int max = 0;
        int preSum = 0;
        for (int i = 0; i < arr.length; i++) {
            preSum += arr[i];
            if (preSumDict.containsKey(preSum - k)) {
                int lastIndex = preSumDict.get(preSum - k);
                int cur = i - lastIndex;
                if (cur > max) {
                    max = cur;
                }
            }
            // 只记录第一次的位置，因为要求最长数组
            if (!preSumDict.containsKey(preSum)) {
                preSumDict.put(preSum, i);
            }
        }
        return max;
    }
}
